package divideAndConquer;

/**
 * 寻找第 k 大的数
 * @author le
 */
public class SearchForMaxNumber
{
    public static void main(String[] args)
    {
        int[] num = {2,3,4,54,67,1,34,8};

        sort(num, 0, num.length-1);
        for (int i : num)
        {
            System.out.println(i);
        }
    }

    /**
     * 从数组中取任意一个值key，将大于key的值放在key右边，小于key的值放在key左边。key的左边和右边则都是有序的了
     * 然后递归key左边的子数组和key右边的子数组，直到每个子数组长度为1，此时，整个数组均有序了
     * @param arr 待输入的数组
     * @param left 左临界值
     * @param right 右临界值
     * @return
     */
    public static int partition(int[] arr,int left, int right){
        int key = arr[left];
        int i = left;
        int j = right;

        while(j > i){
            while(arr[j] < key && j > i){
                j--;
            }
            if (j > i){
                arr[i] = arr[j];
                i++;
            }
            while(arr[i] > key && i < j){
                i++;
            }
            if (j > i){
                arr[j] = arr[i];
                j--;
            }

        }
        arr[i] = key;
        return i;
    }

    public static void quickSort(int[] arr,int left, int right){
        if (left >= right){
            return;
        }
        int i = partition(arr, left,right);
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }

    public static void sort(int[] arr, int left, int right){
        if(left < right){
            int key = arr[left];

            int i = left;
            int j = right;

            while(i < j){
                while(i < j && arr[j] > key){
                    j--;
                }
                if (i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key){
                    i++;
                }
                if (i < j){
                    arr[j--] = arr[i];
                }
                arr[i] = key;
                sort(arr, left, i-1);
                sort(arr,i+1,right);
            }
        }


    }
}
